package likou.bfs;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/29 23:46
 */
public class _773 {
    public static void main(String[] args) {
        System.out.println(slidingPuzzle(new int[][]{{1,2,3}, {4,5,0}}));
    }
    public static int slidingPuzzle(int[][] board) {
        Deque<String> leftDeque = new LinkedList<>();
        Deque<String> rightDeque = new LinkedList<>();

        Set<String> leftSet = new HashSet<>();
        Set<String> rightSet = new HashSet<>();

        String now = "" + board[0][0] + board[0][1] + board[0][2] + board[1][0] + board[1][1] + board[1][2];

        leftDeque.offer(now);
        leftSet.add(now);
        if (leftSet.contains("123450")){
            return 0;
        }
        rightDeque.offer("123450");
        rightSet.add("123450");
        int res = 1;
        while (leftDeque.size() > 0) {
            int n = leftDeque.size();
            for (int i = 0; i < n; i++) {
                now = leftDeque.poll();
                if (getNext(now, leftDeque, leftSet, rightSet)) {
                    return res;
                }
            }
            res++;

            n = rightDeque.size();
            for (int i = 0; i < n; i++) {
                now = rightDeque.poll();
                if (getNext(now, rightDeque, rightSet, leftSet)) {
                    return res;
                }
            }
            res++;
        }
        return -1;
    }


    public static boolean getNext(String str, Deque<String> deque, Set<String> nowSet, Set<String> otherSet) {
        int index = str.indexOf("0");
        char[] chars = str.toCharArray();
        if (index % 3 < 2) {//能往右
            char temp = chars[index + 1];
            chars[index + 1] = chars[index];
            chars[index] = temp;
            String now = String.valueOf(chars);
            if (otherSet.contains(now)) {
                return true;
            }
            if (!nowSet.contains(now)) {
                deque.offer(now);
                nowSet.add(now);
            }
        }
        chars = str.toCharArray();
        if (index % 3 > 0) {//能往左
            char temp = chars[index - 1];
            chars[index - 1] = chars[index];
            chars[index] = temp;
            String now = String.valueOf(chars);
            if (otherSet.contains(now)) {
                return true;
            }
            if (!nowSet.contains(now)) {
                deque.offer(now);
                nowSet.add(now);
            }
        }
        chars = str.toCharArray();
        if (index / 3 == 0) {//能往下
            char temp = chars[index + 3];
            chars[index + 3] = chars[index];
            chars[index] = temp;
            String now = String.valueOf(chars);
            if (otherSet.contains(now)) {
                return true;
            }
            if (!nowSet.contains(now)) {
                deque.offer(now);
                nowSet.add(now);
            }
        }
        chars = str.toCharArray();
        if (index / 3 > 0) {//能往上
            char temp = chars[index - 3];
            chars[index - 3] = chars[index];
            chars[index] = temp;
            String now = String.valueOf(chars);
            if (otherSet.contains(now)) {
                return true;
            }
            if (!nowSet.contains(now)) {
                deque.offer(now);
                nowSet.add(now);
            }
        }
        return false;
    }
}
